package sort;

import java.util.Arrays;

/**
 * @Auther Jun jie Yi
 * @Date 14:04 2021/7/12
 */
public class Sort {
    public static void main(String[] args) {
        int[] arr = {5, 4, 3, 2, 1};

        ShellSort(arr);
        Arrays.stream(arr).forEach(System.out::println);
    }

    /**
     * 直接插入算法的时间复杂度为O(n*n)
     *
     * @param arr
     * @return
     */
    public static int[] insertSort(int[] arr) {
        int i, j;
        int temp;//设置哨兵
        for (i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i - 1]) {
                temp = arr[i];
                for (j = i - 1; j >= 0 && arr[j] > temp; j--) {
                    arr[j + 1] = arr[j];
                }
                arr[j + 1] = temp;
            }
        }
        return arr;
    }
    //折半插入排序(这里采用二分查找法，对直接插入排序进行优化)

    /**
     * 希尔排序的时间复杂度为O(n*logn)
     *
     * @param arr
     */
    public static void ShellSort(int[] arr) {
        int n = arr.length;
        int d = n / 2; //设置起始增量
        while (d >= 1) //增量为1时排序结束
        {
            for (int k = 0; k < d; ++k) //遍历所有的子序
            {
                for (int i = k + d; i < n; i += d) //对每个子序进行插入排序
                {
                    int temp = arr[i];
                    int j = i - d;
                    while (j >= k && arr[j] > temp) {
                        arr[j + d] = arr[j];
                        j -= d;
                    }
                    arr[j + d] = temp;
                }
            }
            d = d / 2; //缩小增量
        }
    }

    /**
     * 冒泡排序(已经用 flag 优化) 时间复杂度为O(n*n)
     * 4 3 2 1 =>
     * 1 4 3 2
     * 1 2 4 3
     * 1 2 3 4
     */
    public static int[] BubbleSort(int[] arr) {
        int len = arr.length;
        int i, j;
        int temp, flag;
        for (i = 0; i < len - 1; i++) {
            flag = 0;
            for (j = len - 1; j > i; j--) {
                if (arr[j] < arr[j - 1]) {
                    temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
                flag = 1;
            }
            if (flag == 0) {
                return arr;
            }
        }
        return arr;
    }

    /**
     * 快速排序 平均时间复杂度为O(n*logn)，最坏时间复杂度为 O(n*n)
     */
    public static void QuickSort(int R[], int low, int high) { //对从R[Low]到R[High]的关键字进行排序

        int temp;
        int i = low, j = high;
        if (low < high) {
            temp = R[low];
            //下面这个循环完成了一趟排序，即数组中小于temp的关键字放在左边，大于temp的关键字放在右边。左边和右边的分界点就是temp的最终位置
            while (i < j) {
                while (i < j && R[j] >= temp)    //先从右往左扫描，找到第一个小于temp的关键字
                    --j;
                if (i < j)        //这个判断保证退出上面的while循环是因为R[j] < temp，而不是因为 i>= j退出循环的，此步非常重要切忌将其忽略
                {
                    R[i] = R[j];    //放在temp左边
                    ++i;            //i右移一位
                }
                while (i < j && R[i] <= temp)    //从右往左扫描，找到一个大于temp的关键字
                    ++i;
                if (i < j) {
                    R[j] = R[i];    //放在tem的左边
                    --j;            //j右移一位
                }
            }
            R[j] = temp;    //将temp放在最终的位置上

            QuickSort(R, low, i - 1);    //递归的对temp左边的关键字进行排序
            QuickSort(R, i + 1, high);    //递归的对temp右边的关键字进行排序
        }
    }

    /**
     * 简单选择排序
     *
     * @param R
     */
    public static void SelectSort(int R[]) {
        int n = R.length;
        int i = 0, j = 0, k = 0;
        int temp = 0;
        for (i = 0; i < n; ++i) {
            k = i;
            //下面这个循环是算法的关键，它从序列中挑选出最小的一个关键字
            for (j = i + 1; j < n; ++j) {
                if (R[k] > R[j])
                    k = j;
            }
            //下面三句完成最小关键字与无序序列的第一个关键字的交换
            temp = R[i];
            R[i] = R[k];
            R[k] = temp;
        }
    }

    //归并排序

    //基数排序
}
